#include <bits/stdc++.h>

using namespace std;
int N=1e6+5;

int main(){
    int n;
    bool isNoPrime[N];
    int cnt[N];
    memset(isNoPrime,0,sizeof(isNoPrime));
    memset(cnt,0,sizeof(cnt));
    isNoPrime[0]=isNoPrime[1]=true;
    for(int i=2;i<N;i++){
        cnt[i]=cnt[i-1];
        if(!isNoPrime[i]){
            cnt[i]++;
            for(int j=2*i;j<N;j+=i){
                isNoPrime[j]=true;
            }
        }
    }
    while(cin >> n){
        while(n--){
            int t;
            cin >> t;
            cout << cnt[t] <<endl;
        }
    }



    return 0;
}